#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
 
ll n;
ll f[71][2];
int li[71];
 
ll dfs(int i,int last,bool limit)
{
    if (i==0) return 1;
    if (!limit&&f[i][last]) return f[i][last];
     
    ll ans=dfs(i-1,0,limit && li[i]==0);
    if (last==0&&(!limit||li[i]==1)) ans+=dfs(i-1,1,limit&&li[i]==1);
     
    if (!limit) f[i][last]=ans;
    return ans;
}
 
ll work1(ll n)
{
    int tot=0;
    while (n)
    {
        li[++tot]=n%2;
        n=n/2;
    }
    return dfs(tot,0,true);
}
struct mat
{
    ll a[3][3];
    int n,m;
    mat() {memset(a,0,sizeof(a));}
    mat operator *(mat b)
    {
        mat c;
        c.n=n,c.m=b.m;
        for (int i=1;i<=c.n;i++) 
            for (int j=1;j<=c.m;j++) 
                for (int k=1;k<=m;k++) c.a[i][j]=(c.a[i][j]+a[i][k]*b.a[k][j]%mod)%mod;
        return c;
    }
};
 
ll work2(ll n)
{
    mat ans,a,tmp;
    tmp.a[1][1]=tmp.a[1][2]=tmp.a[2][1]=1;tmp.n=tmp.m=2;
    ans.a[1][1]=ans.a[2][2]=1;ans.n=ans.m=2;
    a.a[1][1]=a.a[2][1]=1;a.n=2,a.m=1;
    while (n) 
    {
        if (n&1) ans=ans*tmp;
        tmp=tmp*tmp;
        n>>=1;
    }
    ans=ans*a;
    return ans.a[1][1];
}
 
void work()
{
    scanf("%lld",&n);
    printf("%lld\n",work1(n)-1);
    printf("%lld\n",work2(n));
}
 
int main()
{
    int T;
    scanf("%d",&T);
    while (T--) work();
    return 0;
}
